<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>求解递推式</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<p>	递推式 (recurrence) 又叫递归式或差分方程,
	它与常微分方程理论中的许多内容平行, 对照学习收获更多!
</p>

<h2>入门</h2>

<h3>等差数列与等比数列</h3>

<ol class="definition">
	不妨设数列的首项为 `x_0`.
	<li>满足递推关系 `x_n = x_(n-1) + d`, `n = 1, 2, cdots`
		的数列称为<b>等差数列</b>, 其中 `d` 为常数.
	</li>
	<li>满足递推关系 `x_n = x_(n-1) * q`, `n = 1, 2, cdots`
		的数列称为<b>等比数列</b>, 其中 `q` 为常数.
	</li>
</ol>

<ol class="theorem">
	<li>等差数列的通项公式为 `x_n = x_0 + n d`,
		前 `n` 项和为
		<span class="formula">
			`sum_(k=0)^(n-1) x_k = sum_(k=0)^(n-1) (x_0 + k d)`
			`= n x_0 + (n(n-1))/2 d`.
		</span>
	</li>
	<li>等比数列的通项公式为 `x_n = q^n x_0`,
		前 `n` 项和为
		<span class="formula">
			`sum_(k=0)^(n-1) x_k = sum_(k=0)^(n-1) q^k x_0`
			`= {x_0 (1-q^n)/(1-q), if q != 1;
				x_0 n, if q = 1:}`.
		</span>
	</li>
</ol>

<ol class="example">
	求解
	<li><b>线性递推式</b> `x_n = a x_(n-1) + d`;</li>
	<li><b>Bernoulli 型递推式</b> `x_n = a x_(n-1) + d a^n`.</li>
	<li><b>高次递推式</b> `x_0 gt 0`, `x_(n+1) = a x_n^m`.
		其中 `a gt 0`, `m in RR`.
	</li>
</ol>

<ol class="solution">
	当然前 2 小题也可以看作一般的常系数线性递推关系来解答. 详见下文.
	<li>`a = 1` 时 `x_n` 即为等差数列. 下设 `a != 1`, 使用待定系数法,
		设 `x_n - c = a(x_(n-1) - c)`, 于是
		`x_n = a x_(n-1) + (1-a) c`, 与原递推式比较得 `c = d//(1-a)`.
		从而 `{x_n - c}` 是以 `a` 为公比的等比数列.
		解得
		<span class="formula">
			`x_n = a^n x_0 + (1-a^n)/(1-a) d`
			`= a^n x_0 + (a^(n-1) + cdots + a + 1)d`.
		</span>
	</li>
	<li>两边同乘以 `a^-n` 得
		<span class="formula">
			`x_n/a^n = x_(n-1)/a^(n-1) + d`,
		</span>
		即 `{x_n/a^n}` 是以 `d` 为公差的等差数列.
	</li>
	<li>取对数得 `ln x_(n+1) = ln a + m ln x_n`. 这是线性递推式, 解为
		<span class="formula">
			`ln x_n = m^n ln x_0 + (1-m^n)/(1-m) ln a`.
		</span>
		于是
		<span class="formula">
			`x_n = x_0^(m^n) * a^((1-m^n)/(1-m))`.
		</span>
	</li>
</ol>

<ol class="theorem">
	用归纳法容易证明以下多项式的重要求和公式
	<li>`sum_(k=1)^n 1 = n`;</li>
	<li>`sum_(k=1)^n k = n^2/2 + n/2 = (n(n+1))/2`;</li>
	<li>`sum_(k=1)^n k^2 = n^3/3 + n^2/2 + n/6` `= (n(n+1)(2n+1))/6`;</li>
	<li>`sum_(k=1)^n k^3 = n^4/4 + n^3/2 + n^2/4` `= ((n(n+1))/2)^2`.</li>
</ol>

<p class="remark">
	这些公式目前是足够的; 我们以后将得出 `sum_(k=1)^n k^m` (`m`
	为非负整数) 的<a href="4.html">公式</a>.
</p>

<p class="example">
	对于非负整数 `m, n`, Ackermann 函数定义为
	<span class="formula">`A(m, n) = {
		n+1, if m = 0;
		A(m-1, 1), if m gt 0 and n = 0;
		A(m-1, A(m, n-1)), if "else";
	:}`</span>
	试计算 `A(0, n)`, `A(1, n)`, `A(2, n)`, `A(3, n)` 的通项公式, 并求
	`A(4, 2)`.
</p>

<ol class="solution">
	<li>`A(0, n) = n+1`.</li>
	<li>`A(1, n) = A(0, A(1, n-1))`
		`= A(1, n-1) + 1`; 故 `A(1, n)` 为等差数列.
		利用 `A(1, 0) = A(0, 1) = 2` 有:
		<span class="formula">
			`A(1, n) = n+2`.
		</span>
	</li>
	<li>`A(2, n) = A(1, A(2, n-1))`
		`= A(2, n-1) + 2`; 故 `A(2, n)` 也为等差数列.
		利用 `A(2, 0) = A(1, 1) = 3` 有:
		<span class="formula">
			`A(2, n) = 2n + 3`.
		</span>
	</li>
	<li>`A(3, n) = A(2, A(3, n-1))`
		`= 2A(3, n-1) + 3`.
		设 `A(3, n) + c = 2(A(3, n-1) + c)`, 解得 `c = 3`.
		利用等比数列通项公式和 `A(3, 0) = A(2, 1) = 5` 有:
		<span class="formula">
			`A(3, n) = 2^(n+3) - 3`.
		</span>
	</li>
	<li>`A(4, 2) = A(3, A(4, 1))`
		`= A(3, A(3, A(4, 0)))`
		`= A(3, A(3, A(3, 1)))`
		`= A(3, A(3, 16-3))`
		`= A(3, 65536-3)`
		`= 2^65536-3`.
	</li>
</ol>

<h3>求和因子</h3>

<p class="example">
	设递推关系为
	<span class="formula">
		`a_n x_n = b_n x_(n-1) + c_n`,
	</span>
	等号两边乘以适当的 `s_n` 得
	<span class="formula">
		`s_n a_n x_n = s_n b_n x_(n-1) + s_n c_n`.
	</span>
	如果 `s_n b_n = s_(n-1) a_(n-1)`, 记 `y_n = s_n a_n x_n`, 就有
	<span class="formula">
		`y_n = y_(n-1) + s_n c_n`,
	</span>
	这一递推式的解为
	<span class="formula">
		`y_n = y_0 + sum_(k=1)^n (y_k - y_(k-1))`
		`= y_0 + sum_(k=1)^n s_k c_k`.
	</span>
	再将 `s_n b_n = s_(n-1) a_(n-1)` 的解
	<span class="formula">
		`s_n = lambda (a_(n-1) cdots a_1 a_0)/(b_n cdots b_2 b_1)`
	</span>
	代入即可, 其中 `lambda` 为任意常数.
</p>

<p class="example">
	`x_1 = 2`, `x_n = 1/((n-1)!) + 1/n x_(n-1)`, `n gt 1`. 求 `x_n`
	通项公式.
</p>

<p class="solution">
	两边同乘以求和因子 `n!`,
	<span class="formula">
		`n! x_n = (n-1)! x_(n-1) + n`
		`= 1! x_1 + sum_(k=2)^n k`
		`= 2 + (n(n+1))/2 - 1`.
	</span>
	所以
	<span class="formula">
		`x_n = 1/(n!) (1 + (n(n+1))/2)`.
	</span>
</p>

<p class="example">
	`x_1 = 1`, `x_n = 1 + 2/n^2 sum_(k=1)^(n-1) k x_k`, `n gt 1`. 求 `x_n`
	通项公式.
</p>

<p class="solution">
	记 `S_n = 2 sum_(k=1)^n k x_k`. 从递推式中解出
	<span class="formula">
		`S_(n-1) = n^2 (x_n - 1)`,
	</span>
	相减得
	<span class="formula">
		`2 (n-1) x_(n-1) = S_(n-1) - S_(n-2)`
		`= n^2 x_n - (n-1)^2 x_(n-1) - (n^2 - (n-1)^2)`.
	</span>
	即
	<span class="formula">
		`n^2 x_n = (n+1)(n-1) x_(n-1) + 2n - 1`.
	</span>
	两边同加 `n^2`, 再同除以 `n(n+1)`,
	<span class="formula">
		`n/(n+1) (x_n + 1) = (n-1)/n (x_(n-1) + 1) + 2/(n+1)`
		`= 1/2 (x_1 + 1) + sum_(k=2)^n 2/(k+1)`
		`= 2 sum_(k=1)^n 1/(k+1)`.
	</span>
	即
	<span class="formula">
		`x_n = 2(1+1/n) sum_(k=1)^n 1/(k+1) - 1`.
	</span>
</p>

<h3>成套方法</h3>

<p>	成套方法 (repertoire method) 适用于线性递推式的方程组.</p>

<p class="example">
	用成套方法求解
	<span class="formula">
		`{ x_1 = alpha,;
		x_(2n) = 2 x_n + beta, n ge 1;
		x_(2n+1) = 2x_n + gamma, n ge 1 :}`
	</span>
</p>

<p class="solution">
	设通解为
	<span class="formula">
		`x_n = alpha a_n + beta b_n + gamma c_n`,
	</span>
	将 `x_n = 1` 代入原方程组得
	<span class="formula">
		`{1 = alpha; 1 = 2 + beta; 1 = 2 + gamma:}`,
	</span>
	从而 `(alpha, beta, gamma) = (1, -1, -1)`. 代入通解有
	<span class="formula">
		`1 = a_n - b_n - c_n`.
	</span>
	类似地, 再将 `x_n = n` 代入原方程组, 得到 `(alpha, beta, gamma) = (1,
	0, 1)`, 然后代入通解有
	<span class="formula">
		`n = a_n + c_n`.
	</span>
	最后, 取 `(alpha, beta, gamma) = (1, 0, 0)`, 代入通解有 `x_n = a_n`,
	代入原方程组有
	<span class="formula">
		`{a_1 = 1; a_(2n) = 2a_n; a_(2n+1) = 2a_n:}`,
	</span>
	用归纳法可以证明其解为 `a_n = 2^m`, 其中 `2^m le n lt 2^(m+1)`.
	现在联立
	<span class="formula">
		`{a_n-b_n-c_n = 1; a_n+c_n = n; a_n = 2^m:}`
	</span>
	最终解为 `x_n = alpha 2^m + beta(2^(m+1)-1-n) + gamma(n-2^m)`.
</p>

<h2>线性递推式</h2>

<h3>一个例子: Fibonacci 数列</h3>

<p class="example">
	求 Fibonacci 数列
	<span class="formula">`f_n = {
		0, if n = 0;
		1, if n = 1;
		f_(n-1) + f_(n-2){::}, if n ge 2;
	:}`</span>
	的通项公式.
</p>

<p class="solution">
	<b>待定系数法化为等差/等比数列</b>
	设
	<span class="formula">
		`f_n = (varphi + psi) f_(n-1) - varphi psi f_(n-2)`,
	</span>
	则 `varphi, psi` 应是方程 `x^2 - x - 1` 的两根, 不妨令
	`varphi, psi = (1 +- sqrt 5)//2`.
	上式变形得到
	<span class="formula">`{
		f_n - varphi f_(n-1) = psi(f_(n-1) - varphi f_(n-2));
		f_n - psi f_(n-1) = varphi(f_(n-1) - psi f_(n-2));
	:}`</span>
	于是 `{f_n - varphi f_(n-1)}`, `{f_n - psi f_(n-1)}` 皆为等比数列.
	由等比数列的通项公式有:
	<span class="formula">
		`f_n - varphi f_(n-1) = psi^(n-1) (f_1 - varphi f_0) =
		psi^(n-1)`,<br/>
		`f_n - psi f_(n-1) = varphi^(n-1) (f_1 - psi f_0) = varphi^(n-1)`.
	</span>
	注意 `varphi psi = -1`, 由上式得到
	<span class="formula">`{
		psi f_n + f_(n-1) = psi^n;
		varphi f_n + f_(n-1) = varphi^n;
	:}`</span>
	解得
	<span class="formula">
		`f_n = 1/sqrt 5 (varphi^n - psi^n)`.
	</span>
</p>

<p class="solution">
	<b>生成函数法</b>
	记 `F(x) = sum_(n=0)^oo f_n x^n`, 于是
	<span class="formula">
		`F(x) = 0 + x + sum_(n=2)^oo (f_(n-1) + f_(n-2)) x^n`
		`= x + sum_(n=1)^oo f_n x^(n+1) + sum_(n=0)^oo f_n x^(n+2)`
		`= x + x F(x) + x^2 F(x)`.
	</span>
	解得
	<span class="formula">
		`F(x) = x/(1-x-x^2)`.
	</span>
	记上式分母的两个零点的相反数为 `varphi, psi = (1 +- sqrt 5)//2`,
	则 `varphi psi = -1`.  通过分解分式,
	<span class="formula">
		`F(x) = 1/sqrt 5(psi/(x + psi) - varphi/(x + varphi))`
		`= 1/sqrt 5(1/(1-varphi x) - 1/(1-psi x))`
		`= 1/sqrt 5 sum_(n=0)^oo [(varphi x)^n - (psi x)^n]`.
	</span>
	于是
	<span class="formula">
		`f_n = 1/sqrt 5(varphi^n - psi^n)`.
	</span>
</p>

<p class="solution">
	<b>特征根法</b>
	将 `f_n = lambda^n` (`lambda != 0`) 代入递推公式, 得
	<span class="formula">
		`lambda^n = lambda^(n-1) + lambda^(n-2)`,
	</span>
	由 `lambda != 0`, 有
	<span class="formula">
		`lambda^2 = lambda + 1`.
	</span>
	这个二次方程的两根记为 `varphi, psi = (1 +- sqrt 5)//2`,
	由线性叠加原理, 该差分方程的通解为
	<span class="formula">
		`f_n = c_1 varphi^n + c_2 psi^n`.
	</span>
	再代入初值条件 `f_0 = 0`, `f_1 = 1`, 有
	<span class="formula">`{
		c_1 + c_2 = 0;
		varphi c_1 + psi c_2 = 1;
	:}`</span>
	解得
	<span class="formula">
		`c_1, c_2 = +- 1/sqrt 5`.
	</span>
	于是 Fibonacci 数列的通项公式是
	<span class="formula">
		`f_n = 1/sqrt 5 (varphi^n - psi^n)`.
	</span>
</p>

<p class="corollary">
	注意 `|psi|  = |1-sqrt 5|//2 lt 1`, 从而对 `n = 0, 1, 2...` 都成立
	`|psi^n/sqrt 5| lt 1/sqrt 5 lt 1/2`. 我们推出: `f_n` 等于最接近
	`varphi^n/sqrt 5` 的整数.
</p>

<p class="remark">
	`varphi = (1+sqrt 5)//2` 即是著名的黄金比例, 它定义为方程 `x^2 = 1 +
	x` 的正根.  利用通项公式容易计算, Fibonacci 数列前后项的比值
	`f_(n+1)//f_n` 的极限是 `varphi`, 因此它在某种意义上是对等比数列
	`varphi^n/sqrt 5` 的逼近.
</p>

<p class="proof">
	现在我们不用通项公式, 只借助递推式来推导极限 `lim_(n to oo)
	f_(n+1)//f_n`. 记 `x_n = f_(n+1)//f_n`, 则
	<span class="formula">
		`x_1 = 1`, `quad x_n = (f_n + f_(n-1))/(f_n) = 1 + 1/x_(n-1)`.
	</span>
	假设 `x_n to a`, 则 `a` 满足
	<span class="formula">
		`a = 1 + 1/a`.
	</span>
	显然 `a` 是正数, 由上式解得 `a = varphi = (1+sqrt 5)//2`.
	下证极限存在. 注意到 `x_n ge 1`, `n = 1, 2, cdots`, 有
	<span class="formula">
		`|x_n - a| = |(1 + 1/x_(n-1)) - (1 + 1/a)|`
		`= |1/x_(n-1) - 1/a|`
		`= |x_(n-1) - a|/(a x_(n-1))`
		`le 1/a |x_(n-1) - a|`
	</span>
	由 `1/a lt 1` 知 `|x_n - a| to 0`, 即 `x_n to a`.
</p>

<div class="example p">
	在 Fibonacci 数列的生成函数
	<span class="formula">
		`F(x) = x/(1-x-x^2)`
	</span>
	中令 `x = 0.1` 得 `F(0.1) = 10/89`. 于是
<pre style="background: transparent">
  0.01
+ 0.001
+ 0.0002
+ 0.00003
+ 0.000005
+ 0.0000008
+ 0.00000013
+ 0.000000021
+ 0.0000000034
+ 0.00000000055
+ 0.000000000089
+ 0.0000000000144
+ ...
= 1/89
</pre>
</div>

<p class="example">
	设有两种译码规则 0 = A 和 00 = B, 现收到一串 `n` 个 0 的序列,
	问有几种不同的解释. 事实上, 设这个数为 `x_n`, 则 `x_1 = 1`, `x_2 = 2`
	(因为两个 0 可以解释为一个 B, 也可以解释为两个 A).
	设 `n ge 3`, 考虑 `n` 个 0 的序列, 若将第一个 0 解释为一个 A, 则余下
	`n-1` 个 0 有 `x_(n-1)` 种解释; 若将前两个 0 解释为一个 B, 则余下
	`n-2` 个 0 有 `x_(n-2)` 种解释.
	<span class="formula">
		`x_n = x_(n-1) + x_(n-2)`, `quad n ge 3`.
	</span>
	注意 `x_1 = f_2`, `x_2 = f_3`, 所以 `x_n = f_(n+1)`.
</p>

<p class="example">
	用数学归纳法可证 `f_(n+1) f_(n-1) - f_n^2 = (-1)^n`,
	反之, 若数列 `{x_n}` 满足 `x_1 = x_2 = 1` 和 `x_(n+1) x_(n-1) - x_n^2
	= (-1)^n`, 则 `x_n = f_n`.
</p>

<h3>常系数齐次线性递推式</h3>

<p>	我们看到, 求解 Fibonacci 数列通项公式的所有方法中, 特征根法计算量最小,
	且抓住了问题的本质. 这一方法很容易推广到一般的常系数线性递推式,
	形如:
	<span class="formula">
		`sum_(i=0)^k a_i x_(n+i) = 0`, `quad a_k != 0`.
	</span>
	将 `x_n = lambda^n` (`lambda != 0`) 代入方程即得到关于 `lambda` 的一元
	`k` 次方程
	<span class="formula">
		`sum_(i=0)^k a_i lambda^i = 0`,
	</span>
	称为递推式的<b>特征方程</b>, 方程左边的 `k`
	次多项式称为<b>特征多项式</b>, 它的根称为<b>特征根</b>.
	事实上, 方程有 `k` 个线性无关的特解
	<span class="formula">
		`x_n = n^j lambda^n`,
		`quad j = 0, 1, cdots, m-1`,
	</span>
	其中 `lambda` 取遍所有不同的特征根, `m` 是 `lambda` 的重数.
	我们来说明它们确实是方程的解, 即证
    <span class="formula">
      `sum_(i=0)^k a_i (n+i)^j lambda^(n+i) = 0`.
    </span>
    这只需证明下面的引理:
</p>

<p class="lemma">
  设 `lambda != 0` 是多项式 `f(x) = sum_(i=0)^k a_i x^i`
  的 `m` 重根 (`m ge 1`), 那么
  <span class="formula">
    `sum_(i=0)^k a_i (n+i)^j lambda^i = 0`,
    `quad j = 0, 1, cdots, m-1`.
  </span>
</p>

<ol class="proof">
  当 `j = 0` 时, 显然 `sum_(i=0)^k a_i lambda^i = 0`. 下面证明分两步:
  <li>先证 `lambda` 是 `f_j(x) = sum_(i=0)^k a_i i^j x^i` 的 `m-j` 重根,
    `j = 0, 1, cdots, m-1` (约定 `0^0 = 1`).
    `j = 0` 的情形, 条件已经给出.  现在设 `j gt 0`, 且 `lambda` 是
    `f_(j-1)(x) = sum_(i=0)^k a_i i^(j-1) x^i` 的 `m-j+1` 重根, 则它是其导式
    <span class="formula">
      `f_(j-1)'(x) = sum_(i=1)^k a_i i^j x^(i-1)`
    </span>
    的 `m-j` 重根, 从而是
    <span class="formula">
      `f_j(x) = sum_(i=0)^k a_i i^j x^i`
      `= sum_(i=1)^k a_i i^j x^i`
      `= x f_(j-1)'(x)`
    </span>
    的 `m-j` 重根 (这是因为 `lambda != 0`).
  </li>
  <li>再设引理的结论对 `j-1` 成立, 则
    <span class="formula">
      `sum_(i=0)^k a_i (n+i)^j lambda^i`
      `= n sum_(i=0)^k a_i (n+i)^(j-1) lambda^i`
      `  + sum_(i=0)^k a_i i (n+i)^(j-1) lambda^i`
      `= n * 0 + sum_(i=0)^k a_i lambda^i sum_(t=0)^(j-1)
      (j-1;t) i^(t+1) n^(j-1-t)`
      `= sum_(t=0)^(j-1) (j-1;t) n^(j-1-t)
      sum_(i=0)^k a_i i^(t+1) lambda^i = 0`.
    </span>
  </li>
</ol>

<p class="remark">
	如果特征方程有 `m` 重零根 `lambda = 0`, 则对应的系数满足
	`a_0 = a_1 = cdots = a_(m-1) = 0`, 且 `a_m != 0`.
	此时令 `y_n = x_(n+m)`, 原方程就化为
	<span class="formula">
		`sum_(i=m)^k a_i x_(n+i)`
		`= sum_(i=0)^(k-m) a_(i+m) y_(n+i) = 0`.
	</span>
	由于 `a_m != 0`, 它的特征方程无零根.
</p>

<p class="remark">
	如果系数 `a_0, a_1, cdots, a_k` 为实数, 而特征方程有复根
	`lambda = r"e"^("i" theta) = r(cos theta + "i"sin theta)`,
	则在特征方程两端同时取其共轭, 容易证明
	`bar lambda = r(cos theta - "i"sin theta)` 也是特征根,
	且和 `lambda` 具有相同重数.
	可以取两个实的特解
	<span class="formula">
		`1/2 n^j (lambda^n + {:bar lambda:}^n) = n^j r^n cos {:n theta:}`,
		<br/>
		`1/(2"i") n^j (lambda^n - {:bar lambda:}^n) = n^j r^n sin {:n
		theta:}`.
	</span>
	来替换对应的复数特解
	`n^j lambda^n` 和 `n^j {:bar lambda:}^n`.
</p>

<p class="example">
	设 `x^2-2x+6 = 0` 的两根为 `alpha, beta`, 求 `alpha^10 + beta^10`.
</p>

<p class="solution">
	构造线性递推式 `x_n = 2 x_(n-1) - 6 x_(n-2)`,
	它的特征方程恰为 `x^2-2x+6 = 0`.
	于是通解为 `x_n = c_1 alpha^n + c_2 beta^n`.
	取 `c_1 = c_2 = 1`, 则 `x_10` 即为所求. 这时满足的初值条件为
	`x_0 = alpha^0 + beta^0 = 2`, `x_1 = alpha + beta = 2`.
	利用递推式迭代计算可得答案 `7552`.
</p>

<p class="solution">
	构造多项式 `f(x) = x^2-2x+6` 的友阵 `bm A = [0, -6; 1, 2]`,
	它的特征多项式恰为 `f(x)`.
	由线性代数的知识知道, `alpha^10+beta^10` 恰好为 `bm A^10` 的迹.
	依次计算 `bm A^2, bm A^4, bm A^8`, 最后得到 `bm A^10 = [6816, **; **,
	736]`. 所以答案是 `6816+736=7552`.
</p>

<p class="example">
	[<a href="https://brilliant.org/practice/binomial-theorem-level-2-3-challenges/?p=3">题源 brilliant.org</a>]
	求 `(sqrt(71)+1)^71 - (sqrt(71)-1)^71` 的个位数.
</p>

<p class="solution">
	将题目改写为 `(1+sqrt(71))^71 + (1-sqrt(71))^71`,
	构造线性递推式 `x_n = 2 x_(n-1) + 70 x_(n-2)`,
	它的两个特征根恰为 `1+-sqrt(71)`. 题目转化为求解 `x_71 (mod 10)`.
	代入初值条件 `x_1 = 2`, 容易知道
	<span class="formula">
		`x_2 -= 4`, `x_3 -= 8`, `x_4 -= 6`, `x_5 = 2` `quad (mod 10)`.
	</span>
	由于 `71 -= 3 (mod 4)`, 所以 `x_71 -= 8 (mod 10)`.
</p>

<p class="example">
	[<a href="https://brilliant.org/practice/binomial-theorem-level-2-3-challenges/?p=4">题源 brilliant.org</a>]
	求 `|__ (sqrt 2+1)^6 __|`.
</p>

<p class="solution">
	记 `x_n = (1+sqrt 2)^n + (1-sqrt 2)^n`.
	容易求得 `x_6 = 198`. 注意到 `(1-sqrt 2)^6 lt 1`,
	所以答案是 `197`.
</p>

<h3>常系数线性非齐次递推式: 比较系数法</h3>

<ol>这类方程的一般形式如
	<span class="formula">
		`sum_(i=0)^k a_i x_(n+i) = f(n)`.
	</span>
	我们的结论是 (证明?):
	<li>当 `f(n) = P(n) lambda^n`, 其中 `P(n)` 是多项式:
		方程有特解 `n^m Q(n) lambda^n`, 其中 `Q(n)` 是次数不超过
		`del P(n)` 的多项式, `m` 是 `lambda` 在特征多项式中的重数,
		如果 `lambda` 不是特征根, 则 `m = 0`.
	</li>
	<li>当 `f(n) = r^n (A(n) cos n theta + B(n) sin n theta)`, 其中
		`A(n)`, `B(n)` 是多项式:
		方程有特解 `n^m r^n (P(n) cos n theta + Q(n) sin n theta)`, 其中
		`P(n)`, `Q(n)` 是次数不超过 `max{del A(n), del B(n)}` 的多项式,
		`m` 是 `r"e"^("i" theta)` 在特征多项式中的重数,
		如果 `r"e"^("i" theta)` 不是特征根, 则 `m = 0`.
	</li>
</ol>

<table>
	<tr>
		<th>`f(n)`</th>
		<th>方程的特解</th>
	</tr>
	<tr>
		<td>`P(n) lambda^n`</td>
		<td>`n^m Q(n) lambda^n`</td>
	</tr>
	<tr>
		<td>`r^n (A(n) cos n theta + B(n) sin n theta)`</td>
		<td>`n^m r^n (P(n) cos n theta + Q(n) sin n theta)`</td>
	</tr>
</table>

<h2>非线性递推式</h2>

<h3>不动点法</h3>

<p>	事实上, 前面所述的特征方程的方法, 也可以推广到非线性的递推式中.
	一般地, 设 `x_(n+1) = f(x_n)`, 我们称方程 `x = f(x)` 的根为函数 `f(x)`
	的不动点. 我们利用不动点来求解一些递推式.
</p>

<ol class="theorem">
	<b>分式线性变换</b>
	设 `f(x) = (a x + b)/(c x + d)`, `a d - b c != 0`, `c != 0`.
	又设 `{x_n}` 满足 `x_1 != f(x_1)`, `x_(n+1) = f(x_n)`, 且 `c x_n + d
	!= 0`, `n = 1, 2, cdots`. 则
	<li>`f(x)` 有两个不同的不动点, 即方程 `x = f(x)` 有两根 `p, q` 时,
		`{(x_n-p)/(x_n-q)}` 是以 `(a-c p)/(a-c q) = (c q+d)/(c p+d)`
		为公比的等比数列;
		特别当公比的模为 `1`, 辐角为 `2pi` 的有理数倍时,
		该数列呈周期性重复.
	</li>
	<li>`f(x)` 只有一个不动点 `p` 时, `{1/(x_n-p)}` 是以 `c/(c p+d) =
		(2c)/(a+d)` 为公差的等差数列.
	</li>
</ol>

<ol class="proof">
	容易计算,
	<span class="formula">
		`f(x) - f(y) = ((a d-b c)(x-y))/((c x+d)(c y+d))`.
	</span>
	<li>若方程 `x = f(x)` 有两个不同的根 `p, q`, 则
		<span class="formula">
			`(x_(n+1) - p)/(x_(n+1) - q)`
			`= (f(x_n) - f(p))/(f(x_n) - f(q))`
			`= (x_n-p)/(x_n-q) (c q+d)/(c p+d)`.
		</span>
		现在证明 `(a-c p)/(a-c q) = (c q+d)/(c p+d)`. 事实上,
		交叉相乘并消去相同的项, 得到
		<span class="formula">
			`(a-d)c q - c^2q^2 = (a-d)c p - c^2p^2`.
		</span>
		但 `p, q` 是方程 `x = f(x)`, 即 `c x^2 - (a-d) x - b = 0`
		的根, 所以上式左右两边都等于 `-b c`.
	</li>
	<li>若方程 `x = f(x)` 只有一根 `p`, 由于 `c != 0`, 有
		`p = (a-d)//(2c)`, 则
		<span class="formula">
			`c p+d = (a+d)//2`,
		</span>
		又此时判别式 `Delta = (a-d)^2 + 4b c = 0`, 有
		<span class="formula">
			`(c p+d)^2 = (a+d)^2/4 = ((a-d)^2+4a d)/4`
			`= a d-b c`.
		</span>
		于是
		<span class="formula">
			`1/(x_(n+1)-p)`
			`= 1/(f(x_n) - f(p))`
			`= ((c x_n+d)(c p+d))/((a d-b c)(x_n-p))`
			`= (c x_n+d)/((c p+d)(x_n-p))`
			`= 1/(x_n-p) + c/(c p+d)`
			`= 1/(x_n-p) + (2c)/(a+d)`.
		</span>
	</li>
</ol>

<ol class="remark">
	<li>现在解释定理对参数的要求.
		显然如果 `a d-b c = 0`, `f(x) = (a x+b)/(c x+d)` 退化为常数.
		如果 `c = 0`, 递推式退化为 `x_(n+1) = a/d
		x_n + b/d`, 为一线性递推式. 可以按照前例解之, 但也可以用不动点法.
		取方程 `x = a/d x + b/d` 的根 `b/(d-a)`, 有
		<span class="formula">
			`x_(n+1) - b/(d-a) = a/d(x_n - b/(d-a))`,
		</span>
		从而得到一等比数列.
	</li>
	<li>若 `f(x)` 的两个不动点是一对共轭复数 `p, q`,
		通项公式中将含有复数, 但容易说明它其实是实数. 事实上, 记
		<span class="formula">
			`(x_(n+1)-p)/(x_(n+1)-q)`
			`= (x_1-p)/(x_1-q) ((a-c p)/(a-c q))^n := k`,
		</span>
		由于 `k` 的分子分母互为共轭, 所以 `bar k = k^-1`.
		于是
		<span class="formula">
			`x_(n+1) = (p-k q)/(1-k)`
			`= ((p-k q)(1-k^-1))/((1-k)(1-k^-1))`
			`= ((p+q) - (k q+k^-1 p))/((1-k)(1-k^-1))`.
		</span>
		分子分母都是实数, 因此 `x_(n+1)` 是实数.
	</li>
</ol>

<p class="example">
	`x_(n+1) = n/(n+2) x_n + 2/(n+2)`.
</p>

<p class="solution">
	这是非常系数的线性递推式. 注意到系数之和为 `1`, 显然特征方程
	`x = n/(n+2) x + 2/(n+2)` 有不动点 `1`. 计算知
	<span class="formula">
		`x_(n+1) - 1 = n/(n+2) (x_n - 1)`.
	</span>
	递推,
	<span class="formula">
		`x_n - 1 = (n-1)/(n+1) (n-2)/n (n-3)/(n-1)`
		`cdots 2/4 1/3 (x_1-1)`
		`= 2/(n(n+1)) (x_1-1)`.
	</span>
</p>

<p class="example">
	`x_(n+1) = 1/2(x_n + a/x_n)`, `a gt 0`.
</p>

<p class="solution">
	这是熟知的开平方根的牛顿迭代公式, 对所有正的初值都收敛到 `sqrt a`.
	为求通项公式, 先求得不动点为 `+- sqrt a`, 再计算
	<span class="formula">
		`(x_(n+1) - sqrt a)/(x_(n+1) + sqrt a)`
		`= ((x_n^2+a)/(2x_n) - sqrt a)/((x_n^2+a)/(2x_n) + sqrt a)`
		`= ((x_n-sqrt a)/(x_n+sqrt a))^2`.
	</span>
	记 `y_n = (x_n-sqrt a)/(x_n+sqrt a)`, 则 `y_(n+1) = y_n^2`.
	利用高次递推式的结果, `y_n = y_0^(2^n)`. 由此可得 `x_n` 的通项公式.
</p>

<h3>三角换元法</h3>

<ol class="example">
	<li>`x_(n+1) = (1+x_n)/(1-x_n)`;</li>
	<li>`x_(n+1) = (2 x_n)/(1-x_n^2)`;</li>
	<li>`x_(n+1) = 1/2 (x_n +- 1/x_n)`;</li>
	<li>`x_(n+1) = 4 x_n^3 - 3 x_n`, 其中 `x_0 in [-1, 1]`;</li>
	<li>`x_(n+1) = 2 x_n^2 - 1`.</li>
</ol>

<ol class="solution">
	<li>令 `x_n = tan theta_n`, 则递推关系可以写为
		<span class="formula">
			`tan theta_(n+1) = (1+tan theta_n)/(1-tan theta_n)`
			`= tan(theta_n+pi/4)`.
		</span>
		从而
		<span class="formula">
			`theta_(n+1) = theta_n + pi/4 + k pi`, `k in ZZ`,<br/>
			`theta_n = theta_0 + (n pi)/4 + k pi`, `k in ZZ`,<br/>
			`x_n = tan(theta_0 + (n pi)/4)`.
		</span>
	</li>
	<li>令 `x_n = tan theta_n`, 并利用恒等式 `tan 2 theta = (2 tan
		theta)/(1-tan^2 theta)`.
	</li>
	<li>令 `x_n = cot theta_n` (和 `"coth" theta_n`), 并利用恒等式
		<span class="formula">
			`cot 2theta = 1/2(cot theta - 1/(cot theta))`,<br/>
			`"coth" 2theta = 1/2("coth"theta + 1/("coth"theta))`.
		</span>
	</li>
	<li>令 `x_n = cos theta_n`, 并利用恒等式 `cos 3 theta = 4 cos^3 theta
		- 3 cos theta`.
	</li>
	<li>`x_0 in [-1, 1]` 时, 令 `x_n = cos theta_n`, 并利用恒等式 `cos 2
		theta = 2 cos^2 theta - 1`. `x_0 gt 1` 时, 令 `x_n = cosh theta_n`
		并利用恒等式 `cosh 2 theta = 2 cosh^2 theta -1`.
		`x_0 lt -1` 时, 有 `x_1 gt 1`, 即化为上一种情形.
	</li>
</ol>

<h2>杂例</h2>

<p class="example">
	[来自群友 我是的的我是]
	反复投一枚硬币, 记投掷总次数为 `X`, 求出现连续 `n` 次正面时 `X`
	的期望.
</p>

<p class="solution">
	用 `x_n` 表示达成连续 `n` 次正面平均所需的次数.
	假设当前已经连续掷出 `n-1` 次正面,
	再掷一次, 如果为正面, 则达成连续 `n` 次正面;
	如果为背面, 则重新来过, 还需掷 `x_n` 次:
	<span class="formula">
		`x_n = x_(n-1) + 1/2 + (1+x_n)/2`.
	</span>
	利用 `x_0 = 0` 解得 `x_n = 2^(n+1) - 2`.
</p>

<p class="solution">
	记投出正面为胜, 背面为负. 用 `x_k` 表示当前已经 `k` 连胜, 距离达成 `n`
	连胜平均还需要玩的对局数. 讨论每种情况的胜负, 列出方程组
	<span class="formula">`{
		x_0 = (1+x_1)/2 + (1+x_0)/2;
		x_1 = (1+x_2)/2 + (1+x_0)/2;
		cdots;
		x_(n-1) = (1+x_n)/2 + (1+x_0)/2;
		x_n = 0;
	:}`</span>
	方程组化为
	<span class="formula">
		`x_k = 2 x_(k-1) - x_0 - 2`, `quad k = 1, cdots, n`,<br/>
		`x_n = 0`.
	</span>
	将通解 `x_k = a 2^k + b` 代入得
	<span class="formula">
		`a 2^k + b = 2(a 2^(k-1)+b) - x_0 - 2`,<br/>
		`a 2^n + b = 0`.
	</span>
	即 `b = x_0 + 2`, `a = -(x_0+2) 2^-n`. 将它们代入 `x_0 = a + b`
	最终解得
	<span class="formula">
		`E X = x_0 = 2^(n+1)-2`.
	</span>
</p>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
